import java.util.ArrayList;
import java.util.Iterator;

public class Putanja {

    ArrayList<Integer> traka;
    String sekvenca;
    String izlaz;
    int metrika;

    public Putanja(ArrayList<Integer> traka, String sekvenca, String izlaz, int metrika) {
	this.traka = traka;
	this.sekvenca = sekvenca;
	this.izlaz = izlaz;
	this.metrika = metrika;
    }

    public Putanja() {
	this(new ArrayList<Integer>(), new String(""), new String(""), 0);
    }

    private Putanja kopiraj() {
	ArrayList<Integer> traka = new ArrayList<Integer>();
	for (int i = 0; i < this.traka.size(); i++) {
	    traka.add(this.traka.get(i));
	}
	String sekvenca = new String(this.sekvenca);
	String izlaz = new String(this.izlaz);
	int metrika = this.metrika;

	Putanja copy = new Putanja(traka, sekvenca, izlaz, metrika);

	return copy;
    }

    private Putanja dodajBit(int bit, String par) {
	int poslednji = this.traka.get(this.traka.size() - 1);

	Putanja copy = this.kopiraj();
	copy.traka.add(Integer.parseInt(Koder.tranzicija[poslednji][bit], 2));
	copy.sekvenca = copy.sekvenca.concat(Koder.izlaz[poslednji][bit]);
	copy.izlaz = copy.izlaz.concat(Integer.toString(bit));
	int temp = 0;
	for (int i = 0; i < 2; i++) {
	    if (Koder.izlaz[poslednji][bit].charAt(i) != par.charAt(i)) {
		temp += 1;
	    }
	}
	copy.metrika += temp;

	return copy;
    }

    static public ArrayList<Putanja> obradiPutanju(Putanja p, String par) {
	ArrayList<Putanja> result = new ArrayList<Putanja>();
	result.add(p.dodajBit(0, par));
	result.add(p.dodajBit(1, par));
	return result;
    }

    static private boolean jednaki(Putanja a, Putanja b) {
	if (a.traka.size() == b.traka.size()) {
	    int cvorA = a.traka.get(a.traka.size() - 1);
	    int cvorB = b.traka.get(b.traka.size() - 1);
	    if (cvorA == cvorB) {
		return true;
	    } else {
		return false;
	    }
	} else {
	    return false;
	}
    }

    static private void ocistilistu(ArrayList<Putanja> lista) {
	int limit = lista.size();
	for (int i = 0; i < limit; i++) {
	    for (int j = i + 1; j < limit; j++) {
		if (Putanja.jednaki(lista.get(i), lista.get(j))) {
		    if (lista.get(i).metrika < lista.get(j).metrika) {
			lista.remove(j);
			j--;
			limit -= 1;
		    }
		    if (lista.get(i).metrika > lista.get(j).metrika) {
			lista.remove(i);
			i--;

			limit -= 1;
			j = limit;
		    }

		}
	    }
	}
    }

    static public ArrayList<Putanja> viterbi(String ulaz) {
	ArrayList<Putanja> temp = new ArrayList<Putanja>();
	ArrayList<Putanja> result = new ArrayList<Putanja>();
	result.add(new Putanja());
	result.get(0).traka.add(0);
	for (int j = 0; j < ulaz.length() - 1; j = j + 2) {
	    Iterator<Putanja> i = result.iterator();
	    while (i.hasNext()) {
		temp.addAll(Putanja.obradiPutanju(i.next(), ulaz.substring(j, j + 2)));
	    }
	    Putanja.ocistilistu(temp);
	    result.clear();
	    result.addAll(temp);
	    temp.clear();
	}
	return result;
    }
}
